UVa/11451 - Water restrictions/11451.2.cpp

   1 #include <iostream>
   2 #include <cassert>
   3 #include <vector>
   4
   5 using namespace std;
   6
   7 int pos[10], m[10], n[10], C, best, S;
   8
   9 //int cantidad = 0;
  10
  11 void backtrack(){
  12   //cantidad++;
  13
  14   for (int i=0, sum = 0; i<S; ++i){
  15     sum += n[i];
  16     if (sum > C) return;
  17   }
  18
  19   int mask = 0;
  20   for (int i=0; i<S; ++i){
  21     if (n[i] > 0){
  22       for (int j=pos[i]-n[i]; j<= pos[i]+n[i]; ++j){
  23         mask = mask | (1<<j);
  24       }
  25     }
  26   }
  27
  28   best >?= __builtin_popcount(mask);
  29
  30   for (int i=0; i<S; ++i){
  31     if (n[i]+1 <= m[i]){
  32       n[i]++;
  33       backtrack();
  34       n[i]--;
  35     }
  36   }
  37 }
  38
  39 int main(){
  40   int T;
  41   cin >> T;
  42   while (T--){
  43     int L;
  44     cin >> L >> S;
  45     for (int i=0; i<S; ++i){
  46       cin >> pos[i];
  47     }
  48     cin >> C;
  49     assert(C <= 11);
  50     for (int i=0; i<S; ++i){
  51       cin >> m[i];
  52     }
  53
  54     best = -1;
  55     //cantidad = 0;
  56     for (int i=0; i<S; ++i){
  57       n[i] = 0;
  58     }
  59     //backtrack();
  60     cout << best << endl;
  61     //cout << "Evalué " << cantidad << " opciones.\n";
  62
  63   }
  64   return 0;
  65 }